◀ Prev · Parts · Full · Next ▶

NP-hard problems vary greatly in their approximability; some, such as the knapsack problem, can be approximated within a multiplicative factor 1 + ϵ ϵ {\displaystyle 1+\epsilon } , for any fixed ϵ ϵ > 0 {\displaystyle \epsilon >0} , and therefore produce solutions arbitrarily close to the optimum (such a family of approximation algorithms is called a polynomial-time approximation scheme or PTAS). Others are impossible to approximate within any constant, or even polynomial, factor unless P = NP, as in the case of the maximum clique problem. Therefore, an important benefit of studying approximation algorithms is a fine-grained classification of the difficulty of various NP-hard problems beyond the one afforded by the theory of NP-completeness. In other words, although NP-complete problems may be equivalent (under polynomial-time reductions) to each other from the perspective of exact solutions, the corresponding optimization problems behave very differently from the perspective of approximate solutions.

◀ Prev · Parts · Full · Next ▶